package main

import "fmt"

/**
请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
- LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
- int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
- void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value。
  如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
**/

type LRUCache struct {
	cap  int
	len  int
	hash map[int]*Node // 存储 key 和节点的映射
	head *Node         // 哨兵头
	tail *Node         // 哨兵尾
	// 加入哨兵的头尾可以用O(1)的时间复杂度来删除和插入节点
	// 因为只存在头插和尾删
}

type Node struct {
	pre, next *Node
	key, val  int
}

func Constructor(capacity int) LRUCache {
	head := &Node{}
	tail := &Node{}
	head.next = tail
	tail.pre = head
	return LRUCache{
		cap:  capacity,
		len:  0,
		hash: make(map[int]*Node),
		head: head,
		tail: tail,
	}
}

func (this *LRUCache) Get(key int) int {
	if n, ok := this.hash[key]; ok {
		this.moveToHead(n)
		return n.val
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if n, ok := this.hash[key]; ok {
		n.val = value
		this.moveToHead(n)
		return
	}
	// 新建并头插
	n := &Node{key: key, val: value}
	this.hash[key] = n
	this.addAfterHead(n)
	this.len++
	if this.len > this.cap {
		this.popTail()
	}
}

// 将节点移动到表头（head 之后）
func (this *LRUCache) moveToHead(n *Node) {
	this.removeNode(n)
	this.addAfterHead(n)
}

// 头插到 head 之后
func (this *LRUCache) addAfterHead(n *Node) {
	n.pre = this.head
	n.next = this.head.next
	this.head.next.pre = n
	this.head.next = n
}

// 从链表摘除节点（原地）
func (this *LRUCache) removeNode(n *Node) {
	prev := n.pre
	next := n.next
	if prev != nil {
		prev.next = next
	}
	if next != nil {
		next.pre = prev
	}
	n.pre, n.next = nil, nil
}

// 弹出真实尾节点（tail 前一个）
func (this *LRUCache) popTail() {
	last := this.tail.pre
	if last == this.head { // 空
		return
	}
	this.removeNode(last)
	delete(this.hash, last.key)
	this.len--
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */
func main() {
	lru := Constructor(2)
	lru.Put(1, 1)
	lru.Put(2, 2)
	fmt.Println(lru.Get(1)) // 返回 1
	lru.Put(3, 3)           // 该操作会使得关键字 2 作废
	fmt.Println(lru.Get(2)) // 返回 -1 (未找到)
	lru.Put(4, 4)           // 该操作会使得关键字 1 作废
	fmt.Println(lru.Get(1)) // 返回 -1 (未找到)
	fmt.Println(lru.Get(3)) // 返回 3
	fmt.Println(lru.Get(4)) // 返回 4
}
